//
//  main.c
//  随机链表的复制
//
//  Created by 仲7 on 2024/11/26.
//

#include"test.h"
typedef struct Node ListNode;
//申请新节点
ListNode* BuyNode(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->val = x;
    newnode->next = newnode->random = NULL;
    return newnode;
}
//复制新链表
void AddNode(ListNode* phead)
{
    ListNode* pcur = phead;
    //从头开始遍历
    while(pcur)
    {
         ListNode* copy = BuyNode(pcur->val);
         //先把 Next 指向原链表的下一位
        ListNode* Next = pcur->next;
        //然后用三个指针把 copy 插入到原链表
        pcur->next = copy;
        copy->next = Next;
        //pcur 后移
        pcur = Next;
    }
}
struct Node* copyRandomList(struct Node* head)
{
    //特殊情况：链表为空，直接返回 NULL；
    if(head == NULL)
    {
        return NULL;
    }
     //复制链表
    AddNode(head);
     //置 random
     ListNode* pcur = head;
     while(pcur)
     {
        //创建三指针遍历链表
        ListNode* Next = pcur->next->next;
        //Next 保存下一个节点，以供 pcur 后移
        ListNode* copy = pcur->next;
        //当原链表中 random 不为空时才能对其解引用并置random 到新节点，否则不进行处理，因为其原本即为 NULL
        if(pcur->random != NULL)
        {
            copy->random = pcur->random->next;
        }
        pcur = Next;
     }
     //断开连接
     pcur = head;
     //创建新链表的头尾节点
        ListNode* newhead,* newtail;
        newhead = newtail = pcur->next;
        //当 pcur 走到尾节点时，新旧链表已被断完，新链表的尾节点本来就是 NULL，所以不用多余操作。
     while(pcur->next)
     {
        //破坏原链表，连接新链表
        pcur = newtail->next;
        newtail->next = pcur->next;
        newtail = newtail->next;
     }
    return newhead;
}
